package Seven_sorts;

import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 */
public class SevenSort {
    private static ThreadLocalRandom random=ThreadLocalRandom.current();
    public static void main(String[] args) {
     int n=1000000;
     int[] arr=SortTest.generaRabdomArrary(n,0,Integer.MAX_VALUE);
     int[] arr1=SortTest.arraryCopy(arr);
     int[] arr2=SortTest.arraryCopy(arr);
     int[] arr3=SortTest.arraryCopy(arr);
     int[] arr4=SortTest.arraryCopy(arr);
     int[] arr5=SortTest.arraryCopy(arr);
     int[] arr6=SortTest.arraryCopy(arr);
     int[] arr7=SortTest.arraryCopy(arr);
     int[] arr8=SortTest.arraryCopy(arr);
     int[] arr9=SortTest.arraryCopy(arr);
//     SortTest.testSort(arr,"selectionSort");
//     SortTest.testSort(arr1,"heapSort");
//     SortTest.testSort(arr2,"selectionSortOP");
//     SortTest.testSort(arr3,"bubbleSort");
//     SortTest.testSort(arr4,"insertionSort");
//     SortTest.testSort(arr5,"insertionSortBS");
//     SortTest.testSort(arr6,"shellSort");
     SortTest.testSort(arr7,"mergeSort");
     SortTest.testSort(arr8,"quickSort");
     SortTest.testSort(arr9,"quickSortHoare");
    }

    /**
     * 快速排序挖坑法
     * @param arr
     */
    public static void quickSortHoare(int[] arr){
        quickSortHoareInternal(arr,0,arr.length-1);
    }

    private static void quickSortHoareInternal(int[] arr, int l, int r) {
        //        //优化2
//        if (r-l<=15){
//            insertionSort(arr,l,r);
//            return;
//        }
        if (l>=r){
            return;
        }
        int p=partitionHoare(arr,l,r);
        //继续在两个子区间进行快速排序
        //小于v的元素
        quickSortHoareInternal(arr,l,p-1);
        //大于v的元素
        quickSortHoareInternal(arr,p+1,r);
    }

    /**
     * 分区法二挖坑法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionHoare(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int pivot=arr[l];
        int i=l;
        int j=r;
        while (i<j){
            //先让j从后往前走到第一个小于v的元素停止
            while(i<j&&arr[j]>=pivot){
                j--;
            }
            arr[i]=arr[j];
            //接着让i从前向后走到第一个大于v的元素
            while (i<j&&arr[i]<=pivot){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=pivot;
        return i;
    }


    /**
     * 快速排序分区方法一
     * @param arr
     */
    public static void quickSort(int[] arr){

        quickSortInternal(arr,0,arr.length-1);
    }

    private static void quickSortInternal(int[] arr, int l, int r) {
//        //优化2
//        if (r-l<=15){
//            insertionSort(arr,l,r);
//            return;
//        }
        if (l>=r){
            return;
        }
        int p=partition(arr,l,r);
        //继续在两个子区间进行快速排序
        //小于v的元素
        quickSortInternal(arr,l,p-1);
        //大于v的元素
        quickSortInternal(arr,p+1,r);
    }

    /**
     *分区方法一
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] arr, int l, int r) {
//        //优化1
//        int randomIndex=random.nextInt(l,r);
//        swap(arr,l,randomIndex);
        int v=arr[l];
        //arr[l+1...j]时小于v的区间，最开始这个区间是没有元素的
        int j=l;
        //arr[j+1...i]时大于v的区间，最开始这个区间也是没有元素的
        for (int i = l+1; i <=r ; i++) {
            if (arr[i]<v){
                swap(arr,i,j+1);
                j++;
            }
        }
        //此时元素j就是最后一个<v的元素，就把v交换到j的位置
        swap(arr,l,j);
        return j;
    }


    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergSortInternal(arr,0,arr.length-1);
    }

    /**
     * 在arr[l..r)上践行归并排序
     * @param arr
     * @param l
     * @param r
     */
    private static void mergSortInternal(int[] arr, int l, int r) {
//        //优化2
//        if (r-l<=15){
//            insertionSort(arr,l,r);
//            return;
//        }
        if (l>=r){
            //此时数组就是有序数组了
            return;
        }
        int mid=l+(r-l)/2;
        mergSortInternal(arr,l,mid);
        mergSortInternal(arr,mid+1,r);
        //此时arr[l...mid)和[mid+1...r)已经有序，此时只需要合并两个数组即可
        merge(arr,l,mid,r);
//        //优化2
//        if (arr[mid]>arr[mid+1]){
//            //前后两个数组还存在乱序时，才需要合并
//            merge(arr,l,mid,r);
//        }
    }

    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l+1; i <=r; i++) {
            for (int j = i; j >=l+1&&arr[j]<arr[j-1]; j--) {
                swap(arr,j,j-1);
            }
        }

    }

    /**
     * 将arr[l...mid)和[mid+1...r)和并为一个大的有序数组[l...r)
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //先创建一个新的数组temp，将子数组的值复制给先数组
        int[] temp=new int[r-l+1];
        for (int i = 0; i <temp.length; i++) {
            //temp的索引下标为0...arr.length-1
            //arr的索引下标为l...r,差了l个单位的偏移量
            temp[i]=arr[i+l];
        }
        //数组1的开始下标
        int i=l;
        //数组2的开始下标
        int j=mid+1;
        for (int k = l; k <=r; k++) {
            if (i>mid){
                //第一个数组已经遍历完毕
                arr[k]=temp[j-l];
                j++;
            }else if(j>r){
                //第二个数组已经遍历完毕
                arr[k]=temp[i-l];
                i++;
            }else if(temp[i-l]<=temp[j-l]){
                //将temp[i-l]写回arr[k]
                arr[k]=temp[i-l];
                i++;
            }else{
                //arr[i-ll]>temp[j-l],就写回temp[j-l]
                arr[k]=temp[j-l];
                j++;
            }
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap= arr.length/2;
        //第一步好第二步
        while (gap>1){
           insertionSortGap(arr,gap);
           gap=gap/2;
        }
        //当gap等于1时，整个大数组已经近乎有序，此时再来一次插入排序
        insertionSort(arr);
    }
    /**
     *插入排序的1替换为gap就是此处的插入排序
     * @param arr
     * @param gap
     */
    private static void insertionSortGap(int[] arr, int gap) {
        for (int i =gap; i < arr.length; i++) {
            for (int j = i; j-gap >=0&&arr[i]<arr[j-gap] ; j-=gap) {
                swap(arr,j,j-gap);
            }
        }
    }

    /**
     * 折半插入排序
     * @param arr
     */
    public static void insertionSortBS(int[] arr){
        //有序区间[0...i)无序区间[i...n)
        for (int i = 0; i < arr.length; i++) {
            int val=arr[i];
            //有序区间时[left...right]
            int left=0;
            int right=i;
            while (left<right){
                int mid=(left+right)/2;
                if (val<arr[mid]){
                    right=mid;
                }else {
                    left=mid+1;
                }
            }
            //搬移[left...i)的元素
            for (int j = i; j >left; j--) {
                arr[j]=arr[j-1];
            }
            //left就是待插入的位置
            arr[left]=val;
        }
    }

    /**
     * 直接插入排序
     * @param arr
     */
    public static void insertionSort(int[] arr){
        for (int i = 1; i < arr.length ; i++) {
            //有序区间[0..1)默认第一个元素已经有序，待排序区间[i...n)
            //选择无序区间的第一个区间的第一个元素，不断向前看选择位置放入
//            for (int j = i; j >=1&&arr[j]<arr[j-1]; j--) {
//                swap(arr,j,j-1);
//            }
            for (int j = i; j >=1; j--) {
                if (arr[j]>arr[j-1]){
                    //arr[i]恰好是有序区间的后一个元素，无序区间的第一个元素
                    break;
                }else {
                    swap(arr,j,j-1);
                }
            }
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1 ; i++) {
            boolean isSSwapped=false;
            for (int j = 0; j < arr.length-i-1 ; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    isSSwapped=true;
                }
            }
            if (!isSSwapped){
                break;
            }
        }
    }
    /**
     * 双向选择排序
     * @param arr
     */
    public static void selectionSortOP(int[] arr){
        int low=0;
        int high= arr.length-1;
        //循环终止条件，当low==high时，无序区间只剩下最后一个元素，此时数组已经有序
        while (low<high){
            int min=low;
            int max=low;
            for (int i = low+1; i <=high; i++) {
                if (arr[i]<arr[min]){
                    min=i;
                }
                if (arr[i]>arr[max]){
                    max=i;
                }
            }
            //此时min对应了最小值索引，交换到无序区间的最前面
            swap(arr,min,low);
            //注意考虑当low==max的情况
            if (low==max){
                max=min;
            }
            swap(arr,max,high);
            low++;
            high--;
        }
    }

    /**
     * 直接选择排序
     * @param arr
     */
    public static void selectionSort(int[] arr){
        //最开始的无序区间[i...n)，有序区间为[]
        for (int i = 0; i < arr.length; i++) {
            //最小元素索引下标
            int min=i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]<arr[min]){
                    min=j;
                }
            }
            //此时min就是最小值的索引，进行交换操作
            swap(arr,i,min);
        }
    }

    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //先将数组调整为最大堆
        for (int i = (arr.length-1-1)/2; i >=0; i--) {
            siftDown(arr,i,arr.length);
        }
        //不断交换堆顶元素到数组末尾
        for (int i = arr.length-1; i >0; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
    /**
     * 元素的交换操作
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    /**
     * 元素下沉操作
     * @param arr
     * @param i
     * @param length
     */
    private static void siftDown(int[] arr, int i, int length) {
        while (2*i+1<length){
            //说明此时还有左子树
            int j=2*i+1;
            if (j+1<length&&arr[j+1]>arr[j]){
                j++;
            }
            //此时j就是左右子树中的最大值索引
            if (arr[i]>arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i=j;
            }
        }
    }
}
